1. Field of Invention
The present invention relates generally to the field of reliably delivering data between computing devices in a communications network using coding and decoding and in particular for the reliable delivery of packets in a broadcast wireless networks, such as military tactical radio networks.
2. Description of Related Art
Computing devices in a communications network transfer data by transmitting data into a communications channel at the source and receiving the data at the destination or destinations. The communications channel can be wired or wireless. Noise and other impairments in the media, such as interference from other computing devices, can cause errors in the data. In general, wired communications media, such fiber optic, cause less errors in the transmitted data than wireless communications media, such as radio frequency (RF), although in practice errors can be caused in both types of media.
The reliable delivery of data over error inducing channels has been the subject of considerable research and is well described in the literature. For example, “Digital Communications Fundamentals and Applications” by Bernard Sklar describes the use of redundancy to control errors. Techniques include: (a) error detection and retransmission where the source encodes the data with additional redundancy (parity) so that destinations can detect when data is in error (or has been lost) and request the source to retransmit the in error (or lost) data, (b) forward error correction where the source encodes the data with additional redundancy (or parity) information so that the receiver and correct in error (or lost) data using additional redundancy information, or (c) a combination of both techniques.
A communications network is a collection of computing devices (also called nodes) that exchange data amongst one another using communication channels or links between each other. In general, a network can be described as a matrix where the nodes are represented by the rows and columns of the matrix and the links are represented by the matrix values. For example, the rows of the matrix could represent source nodes, the columns of the matrix could represent destination nodes, and the values in the matrix could represent the probability that data transmitted from a source is received at a destination without being repeated (or relayed) by an intermediate node. A value of 1 would represent a link that causes no errors, a value of 0 would represent a link that always cause data to be in error or lost, and a value between 1 and 0 would indicate a link that sometimes causes data to be bad (in error or lost) and sometimes to be good (received correctly). There may be multiple matrixes representing multiple separate (independent) media in use by the network. Separate: media could be multiple separate wired links or multiple RF frequencies. The matrix is said to represent the topology of a given network.
Links can be point to point for a given media (such as many wired links) in which case the row for a given transmitter node is non-zero for the receiver node and zero for all other nodes. Links can be point-to-multipoint for a given media (such as original Ethernet local area networks or current 802.11 wireless LANs) in which case the row for a given transmitter node has more than one non-zero value to indicate that multiple nodes can receive data with some probability. In general for wireless links, nodes that are closer to a transmitter will receive data with higher probability than nodes that are far away.
Often many nodes have a zero or low probability link to many other nodes in the network. In those cases, the nodes exchange link information to find good routes between nodes so that data can be relayed from source nodes to destination nodes through intermediate nodes (called relay nodes). Such a network is called a multihop network. Often a link probability threshold is chosen, so that links with a probability higher than that threshold are called good links and links with a probability lower than that threshold are called bad links. Nodes with good links between one another are called good neighbors and nodes with bad, but non-zero probability, links between one another are called bad neighbors. Nodes with zero links between one another are not considered neighbors at all.
The transfer of data from a source node to a destination node, either directly or though the use of a relay node (or nodes), is called forwarding. Network routing protocols use good links to build network routing tables used in the forwarding of forwarding of data. Example routing protocols include Routing Information Protocol (RIP) and Open Shortest Path First (OSPF).
A mobile ad-hoc network (MANET) is a self-configuring network of mobile router nodes forming a topology of nodes interconnected by wireless links. The topology could be single hop, fully connected where all nodes are directly reachable by all other nodes across a wireless link, or the topology could be multi-hop, sparsely connected, where some nodes are not directly reachable by all of the other nodes, and packets have to be forwarded through relay nodes. Example wireless nodes include networks used in military tactical operations to interconnect warfighting platforms such as tanks and aircraft.
The Open System Interconnection (OSI) Model is an internationally recognized standard architecture that defines a framework for implementing protocols in seven hierarchical layers. Data is passed from one layer to the next, starting at the application layer in one node, and proceeding to the bottom layer, over the channel to the next node and back up the hierarchy. Layers in the OSI protocol stack include layer 1, the physical layer (signals that represent the information in the channel); layer 2, the MAC layer (data link, transmits data packets from transmitter node to receiver node based on node link addresses); layer 3, the network layer (routes data from source node to destination node using relay nodes as required based on node network address); layer 4, the transport layer (ensures delivery of entire message or file end-to-end from source node to destination node); layer 5, the session layer (starts, stops session); layer 6, the presentation layer (encryption, data conversion); layer 7, the application layer. Layers are omitted in some networks, such as the Internet.
For example, a file transfer of data from a source node to a destination node could consist of data at a source node that is transferred from the source node to a destination node using the File Transfer Protocol (FTP) at layer 7. The FTP data is send down to the Transport Control Protocol (TCP) at layer 4. The TCP data is encapsulated into an Internet Protocol (IP) packet at the source node and then forwarded to the destination node directly if it is one link away or to a relay node if the destination one is more than one link away. The IP packet is encapsulated into an IEEE 802.11 wireless local area network (WLAN) packet to be transferred across the link. The WLAN packet is then handed to the physical layer for actual transmission on the wireless RF media. Typically several neighboring nodes will hear the transmission and the neighboring node that is addressed in the WLAN packet will forward it up the protocol stack. The IP packet is extracted out of the WLAN packet at the intended receiving node. If the IP packet is not at the destination node, the packet is again forwarded toward the destination node. If the IP packet is at the destination node, it is passed up to TCP where the data is extracted and passed to FTP.
The reliable delivery techniques discussed above can be implemented at multiple layers of the OSI model, including typically the physical, data link, network, or transport layers. For example, the Transport Control Protocol (TCP) at layer 4 in a source node adds parity information to data packets that it originates. The TCP data is then examined for errors or missing data when it is received at the destination node. Acknowledgements are then sent back from the destination to the source to request additional new data or the resending of incorrectly received data. This data reliability is considered to be end-to-end (ETE)_between source and destination nodes. The 802.11 WLAN at layers 1 and 2 at a transmitting node also adds parity information to data packets that it transmits across a link. The 802.11 WLAN parity information at layer 1 can be used to correct some errors, but not all errors, in a packet at a receiving node. This is called forward error correction (FEC). The 802.1 WLAN data is examined for uncorrectable errors or missing data when it is received at the neighboring receiving nodes. Acknowledgements are then sent back from a receiver to the transmitter to request additional new data or the resending of incorrectly received data. This data reliability is considered to be hop-to-hop between the transmitting and receiving nodes.
In many networks, such as 802.11 WLAN using omni-directional antennas, many other neighboring nodes other than the intended receiver may receive the transmissions as well. These other neighboring nodes examine the intended receiver address and discard the packet (called an overheard packet) if it is not addressed to them. A packet may be overheard by a node farther long in route from the source to destination but may still be discarded.
A source node may intend to deliver data to a single destination node (unicast delivery), to multiple destination nodes (multicast delivery), or to all nodes in a network (broadcast delivery). Similarly, packets may be intended for transmission across a link to a single neighboring node (unicast transmission), to multiple neighboring nodes (multicast transmission), or to all good neighboring nodes (broadcast transmission).
Reliable delivery of data to a single node (unicast delivery or transmission) is performed using FEC and acknowledgement and retransmission of in error or missing packets. Reliable delivery of data to multiple nodes (multicast delivery or transmission) or all nodes (broadcast delivery or transmission) is also performed using FEC and acknowledgment and retransmission of errored or missing packets. A multicast may have problems over a lossy link in a multicast where each node loses a small number of packets, but overall, over all the nodes, the small losses requires retransmission of a significant number of packets.
Fountain codes, also known as rateless erasure codes, are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. Fountain codes help solve retransmission problems for multicasts and have an ability to create an almost endless number of recovery symbols. Fountain codes include raptor codes, LT codes, and online codes. Reed-Solomon codes, an error-correcting code that works by oversampling a polynomial constructed from data, have similar properties but with a smaller number of recovery symbols.
In the prior art, one problem with fountain codes, that is overcome by the present invention, is that the systems employing fountain codes do not take advantage of overheard packets, which increases overhead, hence reduces throughput and increases latency.
Further, current state of the art, involves rateless (e.g. fountain code), sparse graph, erasure code transmissions, and reduce automatic repeat request (ARQ) retransmissions, especially for multicast traffic. In such prior systems, the network FEC coding is either applied end-to-end or hop-by-hop but does not take advantage of overheard packets in multi-hop networks. End-to-end encoding uses ARQ for packets that are not delivered and relay nodes cannot take advantage of overheard packets to improve per-hop reliability, and ultimately throughput and latency. Hop-by-hop encoding sends the entire network encoded block across a single link and then repeats on the next link so that relay nodes cannot take advantage of overheard packets to improve per-hop reliability, throughput and latency.
Consequently, what is lacking in the prior art is a superior way of reliably delivering data to take advantage of overheard packets, in particular during a multicast.